package advanced.class06;

import java.util.HashMap;

public class Test {
    // 测试换钱的方法数
    public static int getMax(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        return process2(arr, 0, aim);
    }

    // 递归体（暴力递归求解）
    public static int process1(int[] arr, int index, int aim) {
        int res = 0;
        // 结束体
        if (index == arr.length) {
            return aim == 0 ? 1 : 0;
        } else {
            for (int i = 0; aim - arr[index] * i >= 0; i++) {
                res += process1(arr, index + 1, aim - (arr[index] * i));
            }
        }
        return res;
    }



    //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    // 纯正改法 ———— 动态规划
    public static int dynamicMethod(int[] arr, int aim){
        if(arr == null || arr.length == 0 || aim < 0){
            return 0;
        }
        // 创建dp数组
        int[][] dp = new int[arr.length + 1][aim + 1];
        // 遍历数组填值
        for (int i = arr.length; i >= 0; i--) {
            for (int j = 0; j <= aim; j++) {
                if(i == arr.length){
                    dp[i][j] = j == 0 ? 1 : 0;
                }else{
                    for (int k = 0; j - arr[i] * k >= 0; k++) {
                        dp[i][j] += dp[i+1][j - arr[i] * k];
                    }
                }
            }
        }
        return dp[0][aim];
    }
    //++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++



    // 解法二： 使用HAshMap进行缓存
    static HashMap<String, Integer> map = new HashMap<>();

    public static int process2(int[] arr, int index, int aim) {
        int res = 0;
        if (index == arr.length) {
            res = aim == 0 ? 1 : 0;
        }else{
            for (int i = 0; aim - arr[index] * i >= 0; i++) {
                String str = (aim - arr[index] * i) + "_" + (index + 1);
                if(map.containsKey(str)){
                    res += map.get(str);
                }else{
                    map.put(str,process2(arr,index + 1,aim-arr[index] * i));
                    res += map.get(str);
                }
            }
        }
        return res;
    }

    // 解法三： 使用二维数组进行缓存
    public static int getMax2(int[] arr, int aim){
        if(arr == null || arr.length == 0 || aim < 0){
            return 0;
        }
        int[][] map = new int[arr.length + 1][aim + 1];
        return process3(arr,0,aim,map);
    }
    public static int process3(int[] arr, int index, int aim, int[][] map){
        int res = 0;
        if (index == arr.length) {
            res = aim == 0 ? 1 : 0;
        } else {
            int mapValue = 0;
            for (int i = 0; aim - arr[index] * i >= 0; i++) {
                mapValue = map[index + 1][aim - arr[index] * i];
                if(mapValue != 0){
                    res += mapValue == -1 ? 0 : mapValue;
                }else{
                    res += process3(arr,index+1,aim - arr[index] * i,map);
                }
            }
            map[index][aim] = res == 0 ? -1 : res;
        }
        return res;
    }
    
    // 解法四： 动态规划
    public static int getMax3(int[] arr, int aim){
        if(arr == null || arr.length == 0 || aim < 0){
            return 0;
        }
        int[][] dp = new int[arr.length][aim + 1];
        // 初始化二维数组第一列
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        // 初始化二维数组的第一行
        for (int i = 0; arr[0] * i <= aim; i++) {
            dp[0][arr[0]*i] = 1;
        }
        int num = 0;
        // 遍历数组填表
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= aim; j++) {
                num = 0;
                for (int k = 0; j - arr[i] * k >= 0; k++) {
                    num += dp[i - 1][j - arr[i] * k];
                }
                dp[i][j] = num;
            }
        }
        return dp[arr.length - 1][aim];
    }

    // 方法4： 优化动态规划
    public static int getMax4(int[] arr, int aim){
        if(arr == null || arr.length == 0 || aim < 0){
            return 0;
        }
        int[][] dp = new int[arr.length][aim + 1];
        // 初始化二维数组第一列
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        // 初始化二维数组的第一行
        for (int i = 0; arr[0] * i <= aim; i++) {
            dp[0][arr[0]*i] = 1;
        }
        int num = 0;
        // 遍历数组填表
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= aim; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
            }
        }
        return dp[arr.length - 1][aim];
    }

    // 方法5: 使用一维数组优化动态规划
    public static int getMax5(int[] arr, int aim){
        if(arr == null || arr.length == 0 || aim < 0){
            return 0;
        }
        int[] dp = new int[aim + 1];
        for (int i = 0; arr[0] * i <= aim; i++) {
            dp[arr[0] * i] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= aim; j++) {
                dp[j] += j - arr[i] >= 0 ? dp[j - arr[i]] : 0;
            }
        }
        return dp[aim];
    }

    // 测试集
//    public static void main(String[] args) {
//        int[] arr = {1, 2, 4, 6, 7};
//        int aim = 10;
//        System.out.println(dynamicMethod(arr, aim));
//    }


    //+++++++++++++++++++++++++++++++++---阿里笔试题----+++++++++++++++++++++++++++++++++++++++++

    /**
     * 问题描述：给定一个机器人，在0-n长度的格子中行走，起始位置为m,移动的步数为p
     * 如果机器人在0位置，那么只能往右走
     * 如果机器任在n位置，那么只能往左走
     * 如果机器人在中间位置，那么即可以往左走也可以往右走
     *
     * 问： 机器任走p步，最终落在k位置有多少种移动的方式
     * @param n
     * @param m
     * @param k
     * @return
     */
    public static int stepNums(int n, int m, int k, int p){
        // 如果越界了，直接返回0
        if(m > n || m < 0) return 0;
        // 如果步数用完了，且当前机器人在k的位置，则返回1
        if(p == 0) return k == m ? 1 : 0;
        // 机器向左走的方式
        return stepNums(n, m + 1, k, p - 1) + stepNums(n, m - 1, k, p - 1);
    }

    //++++++++++++++++++++--------改动态规划---------++++++++++++++++++++
    public static int stepNums2(int n, int m, int k, int p){
        if(m > n || m < 0 || p < 1 || k < 0 || k > m){
            return 0;
        }
        int[][] dp = new int[p+1][n+1];
        for (int i = 0; i <= p; i++) {
            for (int j = 0; j <= n; j++) {
                if(i == 0){
                    dp[i][j] = j == m ? 1 : 0;  // 出发点是m, 所以初始化m点的位置是1
                }else if(j == 0){
                    dp[i][j] = dp[i-1][j+1];
                }else if(j == n){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];
                }
            }
        }
        return dp[p][k];
    }

    public static void main(String[] args) {
        int res = stepNums(10,5,3,20);
        int res1 = stepNums2(10,5,3,20);
        System.out.println(res);
        System.out.println(res1);
    }

    public static int getMaxLen(int[] arr, int aim){
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        int sum = 0;
        int maxLen = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if(map.containsKey(aim - sum)){
                maxLen = Math.max(maxLen,i - map.get(aim - sum));
            }
            if(!map.containsKey(sum)){
                map.put(sum,i);
            }
        }
        return maxLen;
    }

}
